package basic.study.wantOffer.chapter5;

import java.util.HashMap;

/**
 * @ClassName Problem50
 * @Description 第一个只出现一次的字符
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/5 15:22
 * @Version 1.0
 */
public class Problem50 {
    /**
     * 第一个重复的字符做法：倒叙遍历一次，找出第一次出现的记录index
     */
    /**
     * 第一个不重读的字符做法：遍历两次，第一次存频次，第二次取对应频次找1，两遍O(n)
     */
    public static char firstNotRepeatingChar(String str) {
        HashMap<Character, Integer> map = new HashMap<>();
        int temp;

        for (int i = str.length()-1; i >= 0; i--) {
            char c = str.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            temp = map.get(c);
            map.put(c, temp + 1);
        }

        for (int i = 0; i < str.length(); i++) {
            if (map.get(str.charAt(i)) == 1) {
                return str.charAt(i);
            }
        }
        return str.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(firstNotRepeatingChar("aabbccdeefgg"));
    }

    class Problem50_ext {
        int index;
        int[] occurence;

        public Problem50_ext() {
            index = 0;
            occurence = new int[256];
            for (int i = 0; i < 256; i++) {
                occurence[i] = -1;
            }
        }

        public void insert(int val) {
            if (occurence[(int)val] == -1) {
                occurence[(int)val] = index;
                index++;
            } else {
                occurence[(int)val] = -2;
            }
        }

        public char getFirst() {
            int minIndex = Integer.MAX_VALUE;
            char ch = '#';
            for (int i = 0; i < occurence.length; i++) {
                if (occurence[i] >= 0 && occurence[i] < minIndex) {
                    minIndex = occurence[i];
                    ch = (char)i;
                }
            }
            return ch;
        }
    }
}
